package com.zp.self.module.level_4_算法练习.算法.广度优先搜索;

import com.zp.self.module.level_4_算法练习.数据结构.二叉树.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author By ZengPeng
 */
public class 力扣_671_二叉树中第二小的节点 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_671_二叉树中第二小的节点().findSecondMinimumValue(TreeNode.initRoot()));
    }

    /**
    题目：给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
     更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。
     给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。
     如果第二小的值不存在的话，输出 -1 。

     示例 1：
     输入：root = [2,2,5,null,null,5,7]
     输出：5
     解释：最小的值是 2 ，第二小的值是 5 。

     示例 2：
     输入：root = [2,2,2]
     输出：-1
     解释：最小的值是 2, 但是不存在第二小的值。

    分析：【P 💜💜】
       1.广度优先遍历
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.  [1,1,1,1,5,1,4]   ，需要判断是否与最小值相同，相同跳过
     **/
    public int findSecondMinimumValue(TreeNode root) {
        int min = root.val, minTwo;
        if(root.left==null) return -1;
        else minTwo= Math.max(root.right.val,root.left.val);
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        while (!deque.isEmpty()){
            TreeNode treeNode = deque.poll();
            if(treeNode.val<min ){
                minTwo =min;
                min = treeNode.val;
           }else if(treeNode.val>min){
               if(min==minTwo ||treeNode.val<minTwo)
                    minTwo = treeNode.val;
           }
        if(treeNode.left!=null) deque.push(treeNode.left);
        if(treeNode.right!=null) deque.push(treeNode.right);
        }
        return minTwo==min? -1:minTwo;
    }
}
